package com.example.demo.tree;



import java.util.*;
import java.util.function.Consumer;
import java.util.function.Predicate;
import java.util.stream.Stream;

public class AvlTree<T>  implements Collection<T> {

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size != 0;
    }

    @Override
    public boolean contains(Object o) {

        if (o == null) {
            return false;
        }
        T x = (T) o ;
        return search(x) != null;
    }

    @Override
    public Iterator<T> iterator() {
        return new InOrderIterator<>(getFirstTreeNode(root));
    }

    @Override
    public Object[] toArray() {
        return new Object[0];
    }

    @Override
    public <T1> T1[] toArray(T1[] t1s) {
        return null;
    }

    @Override
    public void forEach(Consumer<? super T> action) {

    }



    @Override
    public boolean add(T t) {
        return addValue(t);
    }

    @Override
    public boolean remove(Object o) {
        return false;
    }

    @Override
    public boolean containsAll(Collection<?> collection) {
        return false;
    }

    @Override
    public boolean addAll(Collection<? extends T> collection){
        throw new UnsupportedOperationException();
    }

    @Override
    public boolean removeAll(Collection<?> collection) {
        throw new UnsupportedOperationException();
    }

    @Override
    public boolean removeIf(Predicate<? super T> filter) {
        throw new UnsupportedOperationException();
    }

    @Override
    public boolean retainAll(Collection<?> collection) {
        throw new UnsupportedOperationException();
    }

    @Override
    public void clear() {

    }

    @Override
    public Spliterator<T> spliterator() {
        throw new UnsupportedOperationException();
    }

    @Override
    public Stream<T> stream() {
        return null;
    }

    @Override
    public Stream<T> parallelStream() {
        return null;
    }

    private transient int size;

    enum TreeStatus {
        LH,
        EH,
        RH
    }

    private final Comparator<? super T> comparator;

    static final class TreeNode<T> {

        TreeStatus treeStatus = TreeStatus.EH;
        T value;
        TreeNode<T> left;
        TreeNode<T> right;
        TreeNode<T> parent;

        public TreeNode(T value) {
            this.value = value;
        }

        public TreeNode(T value, TreeNode<T> p) {
            this.value = value;
            this.parent = p;
        }

        @Override
        public String toString() {
            return "value=" + value.toString();
        }
    }

    private int modCount;

    private TreeNode<T> root = null;


    public AvlTree() {
        this.comparator = null;
    }

    public AvlTree(Comparator<? super T> comparator) {
        this.comparator = comparator;
    }


    public boolean addValue(T value) {

        if (value == null) {
            throw new NullPointerException("value不可以为空");
        }

        if (comparator == null && !(value instanceof Comparable)) {
            throw new NullPointerException("comparator不可以为空");
        }

        if (root == null) {
            ++size;
            ++modCount;
            root = new TreeNode<T>(value);
            return true;
        }

        TreeNode<T> parent ;
        TreeNode<T> p = root ;
        int cmp  ;

        if (comparator != null) {
            Comparator<? super T> cpr = comparator;

            do {
                parent = p;
                cmp = cpr.compare(value, p.value);
                if (cmp == 0) {
                    return false;
                } else if (cmp < 0) {
                    p = p.left;
                } else {
                    p = p.right;
                }
            } while (p != null);
        }else {

            Comparable<T> k = (Comparable<T>) value ;

            do {
                parent = p;
                cmp = k.compareTo(p.value);
                if (cmp == 0) {
                    return false;
                } else if (cmp < 0) {
                    p = p.left;
                } else {
                    p = p.right;
                }
            } while (p != null);
        }

        TreeNode<T> newNode = new TreeNode<>(value,parent) ;

        if(cmp < 0){
            parent.left = newNode ;
        }else {
            parent.right = newNode ;
        }


        fixAfterInsert(parent, newNode);
        ++size;
        ++modCount;
        return true;
    }



    private void fixAfterInsert(TreeNode<T> pp, TreeNode<T> p) {

        while (pp.treeStatus == TreeStatus.EH) {

            if (pp.left == p) {
                pp.treeStatus = TreeStatus.LH;
            } else {
                pp.treeStatus = TreeStatus.RH;
            }

            if (pp.parent == null) {
                return;
            }
            pp = pp.parent;
            p = p.parent;
        }



        //  如果pp的状态为RH   分两种情况
        //  情况1  父节点为pp的左孩子
        //  情况2  父节点为pp的右孩子
        if (pp.treeStatus == TreeStatus.RH) {

            if (pp.left == p) {
                pp.treeStatus = TreeStatus.EH;
            } else {

                if (p.treeStatus == TreeStatus.RH) {
                    // RR 旋转
                    RR(pp, p, null);
                } else {
                    //  RL 旋转
                    RL(pp, p, p.left);
                }
            }
        } else {

            if (pp.right == p) {
                pp.treeStatus = TreeStatus.EH;
            } else {

                if (p.treeStatus == TreeStatus.RH) {
                    // LR 旋转
                    LR(pp, p, p.right);
                } else {
                    //  LL 旋转
                    LL(pp, p, null);
                }
            }
        }
    }


    public boolean delValue(T value) {

        TreeNode<T> searched = search(value);

        if (searched == null) {
            return false;
        }

        modCount++;
        int expectedModCount = modCount;
        size--;
        delTreeNode(searched);

        //  愚昧的我，这并不能解决问题
        //  单线程根本不需要进行如此判断，
        //  多线程在并发不高的情况亦不需要如此进行
        //  高并发如此检测只是让程序崩溃退出，
        //  非高并发的情况下可以使用此类
        if (expectedModCount != modCount) {
            throw new ConcurrentModificationException();
        }

        return true;
    }


    private TreeNode<T> search(T value) {

        TreeNode<T> cur = root;

        while (cur != null) {
            int result = compare(value, cur.value);
            if (result == 0) {
                return cur;
            } else if (result < 0) {
                cur = cur.left;
            } else {
                cur = cur.right;
            }
        }

        return null;
    }


    private void delTreeNode(TreeNode<T> cur) {

        // 叶子节点
        if (cur.left == null && cur.right == null) {

            TreeNode<T> p = cur.parent;
            if (p == null) {
                root = null;
                return;
            }

            if (p.left == cur) {
                p.left = null;
                adjustTree(p, null);
            } else {
                p.right = null;
                adjustTree(p, null);
            }

        } else if (cur.left != null && cur.right != null) {

            if (cur.left.right == null) {

                TreeNode<T> l = cur.left;
                TreeNode<T> ll = l.left;

                cur.value = l.value;
                cur.left = ll;

                if (ll != null) {
                    ll.parent = cur;
                }

                adjustTree(cur, cur.left);

            } else {

                TreeNode<T> lm = getMaxOfLeft(cur.left);

                lm.parent.right = lm.left;
                if (lm.left != null) {
                    lm.left.parent = lm.parent;
                }
                cur.value = lm.value;
                adjustTree(lm.parent, lm.parent.right);
            }

        } else if (cur.left != null) {


            if (cur == root) {
                root = cur.left;
                root.parent = null;
                return;
            }

            TreeNode<T> l = cur.left;
            TreeNode<T> p = cur.parent;

            if (l != null) {
                l.parent = p;
            }

            if (p.left == cur) {
                p.left = l;
            } else {
                p.right = l;
            }

            adjustTree(p, l);
        } else {

            if (cur == root) {
                root = cur.right;
                root.parent = null;
                return;
            }

            TreeNode<T> r = cur.right;
            TreeNode<T> p = cur.parent;

            if (r != null) {
                r.parent = p;
            }

            if (p.left == cur) {
                p.left = r;
            } else {
                p.right = r;
            }

            adjustTree(p, r);
        }
    }


    private void adjustTree(TreeNode<T> pp, TreeNode<T> p) {

        while (pp != null) {

            boolean flag = (pp.treeStatus == TreeStatus.EH);

            if (pp.left == null && pp.right == null) {
                pp.treeStatus = TreeStatus.EH;
            } else if (pp.left == p) {
                pp = adjuetRight(pp);
            } else {
                pp = adjuetLeft(pp);
            }

            if (flag) {
                break;
            }

            // LE或者RE型
            if (pp.treeStatus != TreeStatus.EH) {
                break;
            }

            p = pp;
            pp = pp.parent;
        }
    }


    private TreeNode<T> getMaxOfLeft(TreeNode<T> cur) {

        while (cur.right != null) {
            cur = cur.right;
        }
        return cur;
    }


    private TreeNode<T> adjuetRight(TreeNode<T> cur) {

        if (cur.treeStatus == TreeStatus.EH) {
            cur.treeStatus = TreeStatus.RH;
            return cur;
        }

        if (cur.treeStatus == TreeStatus.LH) {
            cur.treeStatus = TreeStatus.EH;
            return cur;
        }

        TreeNode<T> right = cur.right;

        if (right.treeStatus == TreeStatus.LH) {
            return RL(cur, right, right.left);
        } else {
            return RR(cur, cur.right, null);
        }
    }


    private TreeNode<T> adjuetLeft(TreeNode<T> cur) {

        if (cur.treeStatus == TreeStatus.EH) {
            cur.treeStatus = TreeStatus.LH;
            return cur;
        }

        if (cur.treeStatus == TreeStatus.RH) {
            cur.treeStatus = TreeStatus.EH;
            return cur;
        }

        TreeNode<T> left = cur.left;

        if (left.treeStatus == TreeStatus.RH) {
            return LR(cur, left, left.right);
        } else {
            return LL(cur, left, null);
        }
    }


    private TreeNode<T> LL(TreeNode<T> pp, TreeNode<T> p, TreeNode me) {

        TreeNode<T> xpp = pp.parent;

        TreeNode<T> pr = p.right;
        p.right = pp;
        pp.parent = p;

        pp.left = pr;

        if (pr != null) {
            pr.parent = pp;
        }

        p.parent = xpp;

        if (xpp != null) {
            if (xpp.left == pp) {
                xpp.left = p;
            } else {
                xpp.right = p;
            }
        } else {
            root = p;
        }

        // LE 型
        if (p.treeStatus == TreeStatus.EH) {
            p.treeStatus = TreeStatus.RH;
            pp.treeStatus = TreeStatus.LH;
        } else {
            pp.treeStatus = TreeStatus.EH;
            p.treeStatus = TreeStatus.EH;
        }

        return p;
    }


    private int compare(T v1, T v2) {
        if (comparator != null) {
            return comparator.compare(v1, v2);
        } else {
            return ((Comparable) v1).compareTo(v2);
        }
    }


    private TreeNode<T> RR(TreeNode<T> pp, TreeNode<T> p, TreeNode me) {

        TreeNode<T> xpp = pp.parent;
        TreeNode<T> pl = p.left;
        p.left = pp;

        pp.parent = p;
        pp.right = pl;

        if (pl != null) {
            pl.parent = pp;
        }

        p.parent = xpp;

        if (xpp != null) {
            if (xpp.left == pp) {
                xpp.left = p;
            } else {
                xpp.right = p;
            }
        } else {
            root = p;
        }

        // RE 型
        if (p.treeStatus == TreeStatus.EH) {
            p.treeStatus = TreeStatus.LH;
            pp.treeStatus = TreeStatus.RH;
        } else {
            pp.treeStatus = TreeStatus.EH;
            p.treeStatus = TreeStatus.EH;
        }

        return p;
    }


    private TreeNode<T> RL(TreeNode<T> pp, TreeNode<T> p, TreeNode<T> me) {

        TreeNode<T> xpp = pp.parent;

        TreeNode<T> left = me.left;
        TreeNode<T> right = me.right;

        me.left = pp;
        me.right = p;

        pp.right = left;
        p.left = right;

        if (left != null) {
            left.parent = pp;
        }

        if (right != null) {
            right.parent = p;
        }

        pp.parent = me;
        p.parent = me;

        if (me.treeStatus == TreeStatus.EH) {
            pp.treeStatus = TreeStatus.EH;
            p.treeStatus = TreeStatus.EH;
        } else if (me.treeStatus == TreeStatus.LH) {
            pp.treeStatus = TreeStatus.EH;
            p.treeStatus = TreeStatus.RH;
        } else {
            pp.treeStatus = TreeStatus.LH;
            p.treeStatus = TreeStatus.EH;
        }

        me.treeStatus = TreeStatus.EH;
        me.parent = xpp;

        if (xpp != null) {
            if (xpp.left == pp) {
                xpp.left = me;
            } else {
                xpp.right = me;
            }
        } else {
            root = me;
        }

        return me;
    }


    private TreeNode<T> LR(TreeNode<T> pp, TreeNode<T> p, TreeNode<T> me) {

        TreeNode<T> xpp = pp.parent;

        TreeNode<T> left = me.left;
        TreeNode<T> right = me.right;

        me.left = p;
        me.right = pp;

        p.right = left;
        pp.left = right;

        if (left != null) {
            left.parent = p;
        }

        if (right != null) {
            right.parent = pp;
        }

        p.parent = me;
        pp.parent = me;


        if (me.treeStatus == TreeStatus.EH) {
            p.treeStatus = TreeStatus.EH;
            pp.treeStatus = TreeStatus.EH;
        } else if (me.treeStatus == TreeStatus.LH) {
            p.treeStatus = TreeStatus.EH;
            pp.treeStatus = TreeStatus.RH;
        } else {
            p.treeStatus = TreeStatus.LH;
            pp.treeStatus = TreeStatus.EH;
        }

        me.treeStatus = TreeStatus.EH;

        if (xpp != null) {
            if (xpp.left == pp) {
                xpp.left = me;
            } else {
                xpp.right = me;
            }
            me.parent = xpp;
        } else {
            root = me;
            me.parent = null;
        }

        return me;
    }


    public boolean checkInvariants() {
        return checkInvariants(root);
    }


    //  循环不变式检测



    private boolean checkInvariants(TreeNode<T> t) {

        if (t == null) {
            return true;
        }

        // 根节点的parent为空
        if (t == root && t.parent != null) {
            return false;
        }

        TreeNode<T> l = t.left;
        TreeNode<T> r = t.right;

        // 都等于空时  t 的状态应该为EH
        if (l == null && r == null) {
            return t.treeStatus == TreeStatus.EH ;
        }

        // 左为空，右不为空
        if (l == null) {
            if (r.parent != t) {
                return false;
            }

            if (t.treeStatus != TreeStatus.RH) {
                return false;
            }

            if (r.left != null || r.right != null) {
                return false;
            }

            if (compare(r.value, t.value) <= 0) {
                return false;
            }

            return true;
        }


        // 右为空，左不为空
        if (r == null) {
            if (l.parent != t) {
                return false;
            }

            if (t.treeStatus != TreeStatus.LH) {
                return false;
            }

            if (l.left != null || l.right != null) {
                return false;
            }

            if (compare(l.value, t.value) >= 0) {
                return false;
            }

            return true;
        }


        // 都不为空

        boolean fl = checkInvariants(l);
        if (!fl) {
            return false;
        }

        boolean fr = checkInvariants(r);
        if (!fr) {
            return false;
        }


        if (compare(l.value, t.value) >= 0 || compare(t.value, r.value) >= 0) {
            return false;
        }

        int lh = getH(l);
        int rh = getH(r);

        if (t.treeStatus == TreeStatus.EH) {
            return (lh == rh);
        } else if (t.treeStatus == TreeStatus.RH) {
            return (rh - lh) == 1;
        } else {
            return (lh - rh) == 1;
        }
    }

    private boolean checkInvariants1(TreeNode<T> t) {

        if (t == null) {
            return true;
        }

        if (t == root && t.parent != null) {
            return false;
        }

        TreeNode<T> l = t.left;
        if (l != null && (l.parent != t || !checkInvariants1(l) || compare(l.value,t.value) >=0)) {
            return false;
        }

        TreeNode<T> r = t.right;
        if (r != null && (r.parent != t || !checkInvariants1(r) || compare(r.value, t.value) <= 0)) {
            return false;
        }

        int lh = getH(l);
        int rh = getH(r);

        if (t.treeStatus == TreeStatus.EH) {
            return (lh == rh);
        } else if (t.treeStatus == TreeStatus.RH) {
            return (rh - lh) == 1;
        } else {
            return (lh - rh) == 1;
        }
    }



    static <T> int getH(TreeNode<T> node) {
        int i = 0;

        while (node != null) {
            if (node.treeStatus != TreeStatus.RH) {
                node = node.left;
            } else {
                node = node.right;
            }
            i++;
        }

        return i;
    }


    static final <T> TreeNode<T> getNext(TreeNode<T> cur) {

        if (cur.right != null) {
            return cur.right;
        }

        if (cur.parent != null && cur.parent.left == cur) {
            return cur.parent;
        }

        return null;
    }


    final static TreeNode getFirstTreeNode(TreeNode root) {
        TreeNode p = root;
        if (p != null) {
            while (p.left != null) {
                p = p.left;
            }
        }
        return p;
    }


    final static TreeNode successor(TreeNode t) {

        if (t == null) {
            return null;
        } else if (t.right != null) {
            TreeNode p = t.right;
            while (p.left != null) {
                p = p.left;
            }
            return p;
        } else {
            TreeNode p = t.parent;
            TreeNode ch = t;
            while (p != null && p.right == ch) {
                ch = p;
                p = p.parent;
            }
            return p;
        }
    }


    final TreeNode<T> predecessor(TreeNode<T> t) {

        if (t == null) {
            return null;
        } else if (t.left != null) {
            TreeNode<T> p = t.left;
            while (p != p.right) {
                p = p.right;
            }
            return p;
        } else {
            TreeNode<T> p = t.parent;
            TreeNode<T> ch = t;
            while (p != null && p.left == ch) {
                ch = p;
                p = p.parent;
            }
            return p;
        }
    }

    final TreeNode<T> getLastEntry() {
        TreeNode<T> p = root;
        if (p != null)
            while (p.right != null)
                p = p.right;
        return p;
    }



    private  class InOrderIterator<T> implements Iterator<T> {

        private TreeNode<T> cur;

        private int expectedModCount ;

        public InOrderIterator(TreeNode<T> first) {
            cur = first;
            expectedModCount = AvlTree.this.modCount;
        }

        @Override
        public final boolean hasNext() {
            checkForComodification();
            return cur != null;
        }

        @Override
        public  T next() {
            checkForComodification();
            T value = cur.value;
            cur = successor(cur);
            return value;
        }

        final void checkForComodification() {
            if (modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }
        }
    }

}
